{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All Numbers Disappeared in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDisappearedNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到所有数组中消失的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个含 <code>n</code> 个整数的数组 <code>nums</code> ，其中 <code>nums[i]</code> 在区间 <code>[1, n]</code> 内。请你找出所有在 <code>[1, n]</code> 范围内但没有出现在 <code>nums</code> 中的数字，并以数组的形式返回结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,3,2,7,8,2,3,1]\n",
    "<strong>输出：</strong>[5,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1]\n",
    "<strong>输出：</strong>[2]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= n</code></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>进阶：</strong>你能在不使用额外空间且时间复杂度为<em> </em><code>O(n)</code><em> </em>的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-numbers-disappeared-in-an-array](https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-numbers-disappeared-in-an-array](https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,7,8,2,3,1]', '[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        i=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[abs(nums[i])-1]>0:\n",
    "                nums[abs(nums[i])-1]*=-1\n",
    "        j=0   \n",
    "        k=1 \n",
    "        while j<len(nums):\n",
    "            if nums[j]<0:\n",
    "                nums.pop(j)\n",
    "                k+=1\n",
    "            else:\n",
    "                nums[j]=k\n",
    "                j+=1\n",
    "                k+=1\n",
    "        return nums            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]==0): continue\n",
    "            this_num = nums[i]\n",
    "            if(this_num==i+1):\n",
    "                nums[i]=0\n",
    "            else:\n",
    "                tmp = nums[this_num-1]\n",
    "                nums[this_num-1]=0\n",
    "                while(tmp!=0):\n",
    "                    tmp2 = nums[tmp-1]\n",
    "                    nums[tmp-1] = 0\n",
    "                    tmp = tmp2\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]>0):\n",
    "                res.append(i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        for num in nums:\n",
    "            while num != -1:\n",
    "                tmp = nums[num-1]\n",
    "                nums[num-1] = -1\n",
    "                num = tmp\n",
    "        res = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num != -1:\n",
    "                res.append(idx+1)\n",
    "        return res\n",
    "\n",
    "    def findDisappearedNumbers1(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        官方评论区更简洁实现版本\n",
    "        用鸽笼原理实现，由题意可得，1~n的位置表示1~n个笼子，如果出现过，相应的“鸽笼”就会被占掉，我们将数字置为负数表示被占掉了。 \n",
    "        最后再遍历一遍，如果“鸽笼”为正数就是没出现的数字。\n",
    "        \"\"\"\n",
    "        for n in nums:\n",
    "            nums[abs(n)-1] = - abs(nums[abs(n)-1])\n",
    "            #找到相应的鸽笼位置，取反\n",
    "\n",
    "        res = []\n",
    "        for i, v in enumerate(nums):\n",
    "            if v >0:#如果大于0，说明没被占过，也就是没有出现过的数字\n",
    "                res.append(i+1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * (len(nums)+1)\n",
    "        ans[0]=1\n",
    "        for i in nums:\n",
    "            ans[i]+=1\n",
    "        nums.clear()\n",
    "        print(len(ans))\n",
    "        for i,value in enumerate(ans):\n",
    "            if value==0 :\n",
    "                nums.append(i)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        这题属于是有一点小技巧的题目，当然在考场上你会更倾向于用哈希表来做，但是留有一个在原数组上建立哈希表的小技巧也是不错的\n",
    "        这题的核心思路在与，哈希表不一定需要额外开辟空间，如果有确定的编解码方法的话，其可以直接在原来的数组上进行编码。在本题中，由于哈希表大小和遍历数列一样大，所以可以直接在原数组上进行键值的编码，即如果这个数出现过，就在其数上面加n，这样我可以通过x%n的操作把原数复原出来，也能通过判定哈希表每个键值是否大与n来判定这个数是否存在过。\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            x = (num-1) % n # 复原键值\n",
    "            nums[x] += n    # 对数组进行编码\n",
    "\n",
    "        ret = [i+1 for i, num in enumerate(nums) if num <= n]\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        由于1<=nums[i]<=n，因此可以将所有nums[i]对应的索引数值置负值\n",
    "        （不能置0，置0有可能改变数组未遍历到的值），最后遍历nums，非0元素的索引即为结果\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        results = []\n",
    "\n",
    "        for num in nums:\n",
    "            nums[abs(num)-1] = -abs(nums[abs(num)-1])\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                results.append(i+1)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        # 完全背包问题似乎比0-1背包问题简单\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            while nums[nums[i]-1] != nums[i]:\n",
    "                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i]-1]\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != i+1:\n",
    "                res.append(i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if not nums[i]:\n",
    "                continue\n",
    "            j = nums[i]-1\n",
    "            while nums[j]:\n",
    "                ind = nums[j] - 1\n",
    "                nums[j] = 0\n",
    "                j = ind\n",
    "        ans = [i for i in range(1, n+1) if nums[i-1]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]\n",
    "            while num != 0:\n",
    "                tmp = nums[num - 1]\n",
    "                nums[num - 1] = 0\n",
    "                num = tmp\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                res.append(i + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        写一中不用额外空间的解法。因为是1~n,直接将对应的位置设置成0，则剩余的整数即为没出现过的。\n",
    "        \"\"\"\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            v = nums[i]\n",
    "            while v:\n",
    "                tem = nums[v-1] \n",
    "                nums[v-1] = 0\n",
    "                v = tem\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]:\n",
    "                res.append(i+1)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == -1:\n",
    "                continue\n",
    "            if nums[i] > n:\n",
    "                nums[i] = -2\n",
    "            else:\n",
    "                temp = nums[nums[i] - 1]\n",
    "                if temp == -1:\n",
    "                    continue\n",
    "                nums[nums[i] - 1] = -1\n",
    "                while temp <= n and nums[temp-1] != -1:\n",
    "                    t = nums[temp-1]\n",
    "                    nums[temp-1] = -1\n",
    "                    temp = t\n",
    "                    #print(temp, nums)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if nums[i] != -1:\n",
    "                res.append(i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1] != 0:\n",
    "                j = nums[i - 1]\n",
    "                while True:\n",
    "                    now = nums[j - 1]\n",
    "                    if now == 0:\n",
    "                        break\n",
    "                    nums[j-1] = 0\n",
    "                    j = now\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] != 0:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if not nums[i]:\n",
    "                continue\n",
    "            else:\n",
    "                j = nums[i] - 1\n",
    "                while nums[j]:\n",
    "                    tmp = nums[j] - 1\n",
    "                    nums[j] = 0\n",
    "                    j = tmp\n",
    "        return [i for i in range(1,n+1) if nums[i-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        for n in nums:\n",
    "            nums[abs(n) - 1] = -abs(nums[abs(n) - 1])\n",
    "        return [i + 1 for i, n in enumerate(nums) if n > 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in nums:\n",
    "            tmp = i\n",
    "            while tmp:\n",
    "                idx = tmp - 1\n",
    "                tmp = nums[idx]\n",
    "                nums[idx] = 0\n",
    "        return [i for i in range(1, n+1) if nums[i-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        numlen = len(nums)\n",
    "        res = []\n",
    "        for i in range(numlen):\n",
    "            if nums[i] == -1:\n",
    "                continue\n",
    "            cur_idx, cur_val = i, nums[i]\n",
    "            while nums[cur_val - 1] != -1:\n",
    "                cur_idx = cur_val - 1\n",
    "                cur_val = nums[cur_idx]\n",
    "                nums[cur_idx] = -1\n",
    "        for i in range(numlen):\n",
    "            if nums[i] != -1:\n",
    "                res.append(i+1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == -1:\n",
    "                continue\n",
    "            tmp = nums[i]-1\n",
    "            while tmp > -1:\n",
    "                a = nums[tmp]-1\n",
    "                nums[tmp] = -1\n",
    "                tmp = a\n",
    "        for i in range(n):\n",
    "            if nums[i] == -1:\n",
    "                continue\n",
    "            ans.append(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        cur = 0 \n",
    "\n",
    "        while cur < len(nums):\n",
    "            if nums[cur] == '*':\n",
    "                cur += 1\n",
    "                continue \n",
    "            \n",
    "            ind = nums[cur] - 1\n",
    "            if nums[ind] == '*':\n",
    "                cur += 1\n",
    "            else:\n",
    "                nums[cur] = nums[ind]\n",
    "                nums[ind] = '*'\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != '*':\n",
    "                res.append(i + 1)\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        count = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            count[nums[i]] += 1\n",
    "        print(count)\n",
    "        res = []\n",
    "        for i in range(1, n + 1):\n",
    "            if count[i] == 0:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        hash = dict()\n",
    "        res = list()\n",
    "        for i in nums:\n",
    "            if i not in hash:\n",
    "                hash[i] = 1\n",
    "        for i in range(1, n+1):\n",
    "            if i not in hash:\n",
    "                res.append(i)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mapping = [0 for i in range(n + 1)]\n",
    "\n",
    "        for item in nums:\n",
    "            mapping[item] = 1\n",
    "        \n",
    "\n",
    "        result = []\n",
    "\n",
    "        for idx, item in enumerate(mapping[1:]):\n",
    "            if item == 0:\n",
    "                result.append(idx + 1)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = {}\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            if i not in n:\n",
    "                n[i]=0\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if i not in n:\n",
    "                ans.append(i)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        trg = set(nums)\n",
    "        for k in range(1,n+1):\n",
    "            if k not in trg:\n",
    "                res.append(k)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        r = [*range(1, len(nums) + 1)]\n",
    "        for n in nums:\n",
    "            r[n - 1] = 0\n",
    "        for k in range(len(r) - 1, -1, -1):\n",
    "            if r[k] == 0:\n",
    "                r.pop(k)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: list[int]) -> list[int]:\n",
    "        nums.extend([0, len(nums) + 1])\n",
    "        nums.sort()\n",
    "        dis_num = []\n",
    "        lens = len(nums)\n",
    "        i = 0\n",
    "        while i < lens - 1:\n",
    "            gap = nums[i + 1] - nums[i]\n",
    "            if gap > 1:\n",
    "                dis_num.extend([x for x in range(nums[i] + 1, nums[i] + gap)])\n",
    "            i += 1\n",
    "        return dis_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: list[int]) -> list[int]:\n",
    "        nums.extend([0, len(nums) + 1])\n",
    "        nums.sort()\n",
    "        dis_num = []\n",
    "        lens = len(nums)\n",
    "        i = 0\n",
    "        while i < lens - 1:\n",
    "            gap = nums[i + 1] - nums[i]\n",
    "            if gap > 1:\n",
    "                dis_num.extend([x for x in range(nums[i] + 1, nums[i] + gap)])\n",
    "            i += 1\n",
    "        return dis_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        l=len(nums)\n",
    "        sz=[]\n",
    "        for i in nums:\n",
    "            x=(i-1)%l\n",
    "            nums[x]+=l\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<=l:\n",
    "                sz.append(i+1)\n",
    "        return sz\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            x = (num - 1) % n\n",
    "            nums[x] += n\n",
    "        \n",
    "        ret = [i + 1 for i, num in enumerate(nums) if num <= n]\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        for i, v in enumerate(nums):\n",
    "            if nums[abs(v)-1] > 0:\n",
    "                nums[abs(v)-1] *= -1\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                res.append(i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            index = i\n",
    "            cur = -1\n",
    "            while nums[index]-1 != index and index >= 0:\n",
    "                tmp = nums[index]\n",
    "                nums[index] = cur\n",
    "                cur = tmp\n",
    "                index = cur - 1\n",
    "            \n",
    "\n",
    "        #print(nums)   \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if i != nums[i] -1:\n",
    "                ans.append(i+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "            tmp = [0] * (len(nums)+1)\n",
    "            for i in nums:\n",
    "                tmp[i] = 1\n",
    "            ans = []\n",
    "            for j in range(1,len(tmp)):\n",
    "                if tmp[j] == 0:\n",
    "                    ans.append(j)\n",
    "            return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        q=[]\n",
    "        re=[0]*(len(nums)+1)\n",
    "        for i in nums:\n",
    "            re[i]+=1\n",
    "        for t in range(1,len(nums)+1):\n",
    "            if re[t]==0:\n",
    "                q.append(t)\n",
    "        return q \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        all_member = [0] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            all_member[nums[i]-1] = 1\n",
    "        dis_nums=[]\n",
    "        for i in range(len(nums)):\n",
    "            if all_member[i] == 0:\n",
    "                dis_nums.append(i+1)\n",
    "        return dis_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        cnt = [0] * (n+1)\r\n",
    "        for x in nums:\r\n",
    "            cnt[x] += 1\r\n",
    "        res = []\r\n",
    "        for i in range(1, n+1):\r\n",
    "            if cnt[i] == 0:\r\n",
    "                res.append(i)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        for i in range(len(nums)):    \n",
    "            if nums[abs(nums[i])-1] > 0:\n",
    "                nums[abs(nums[i])-1] *= -1\n",
    "\n",
    "        res = []\n",
    "        print(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                res.append(i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[abs(nums[i])-1] > 0:\n",
    "                nums[abs(nums[i])-1] = (-1) * nums[abs(nums[i])-1]\n",
    "        res = []\n",
    "        print(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                res.append(i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        counter=set(nums)\n",
    "        n=len(nums)\n",
    "        temp=[]\n",
    "        for i in range (1,n+1):\n",
    "            if i not in counter:\n",
    "                temp.append(i)\n",
    "            \n",
    "        return temp\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)  # 8\n",
    "\n",
    "        maphash = [False] * (n+1)\n",
    "        res = []\n",
    "        for i in range(0, n):  # nums[0] - nums[7]\n",
    "            maphash[nums[i]] = True   # 1 2 3 4 7 8\n",
    "\n",
    "        for i in range(0, n+1):\n",
    "            if i != 0 and maphash[i] == False:\n",
    "                res.append(i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        cnt = set(nums)\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            if i not in cnt:\n",
    "                ans.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            num = int(nums[i])\n",
    "            nums[num - 1] = str(nums[num - 1])\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if type(nums[i]) == int:\n",
    "                res.append(i + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        a = []\n",
    "        j = 0\n",
    "        m = len(nums)\n",
    "        for i in range(1,n+1):\n",
    "            if i!=nums[j]:\n",
    "                a.append(i)\n",
    "            else:\n",
    "                j += 1\n",
    "                if j==m:\n",
    "                    a += [k for k in range(i+1,n+1)]\n",
    "                    break\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        set0=set(list([i+1 for i in range(len(nums))]))\n",
    "        for x in nums:\n",
    "            if x in set0:\n",
    "                set0.remove(x)\n",
    "        return list(set0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        d = set(nums)\n",
    "        fast = 0\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if i not in d:\n",
    "                nums[fast] = i\n",
    "                fast = fast + 1\n",
    "        return nums[:fast:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        nums = set(sorted(nums))\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            if i not in nums:\n",
    "                ans.append(i)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        val_set = set(list(range(1, n+1)))\n",
    "        for val in nums:\n",
    "            if val in val_set:\n",
    "                val_set.remove(val)\n",
    "        return list(val_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n, hashmap, res = len(nums), {}, []\n",
    "        for num in nums:\n",
    "            hashmap[num] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if i not in hashmap.keys():\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        hashlist = {}\n",
    "        for i in nums:\n",
    "            if i in hashlist:\n",
    "                hashlist[i] += 1\n",
    "            else:\n",
    "                hashlist[i] = 1\n",
    "        ans = []\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            if i not in hashlist:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        s1=set(nums)\n",
    "        list1=[]\n",
    "        for i in range(1,n+1):\n",
    "            if i not in s1:\n",
    "                list1.append(i)\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        dict = {}\n",
    "        res = []\n",
    "        for a in nums:\n",
    "            if a not in dict:\n",
    "                dict[a] = 1\n",
    "        for i in range(len(nums)):\n",
    "            if (i+1) not in dict:\n",
    "                res.append(i+1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "#         nums_set = set(nums)\n",
    "#         n = len(nums)\n",
    "#         res = []\n",
    "#         for i in range(1, n+1):\n",
    "#             if i not in nums_set:\n",
    "#                 res.append(i)\n",
    "#         return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        nums_set = set(nums)\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for i in range(1, n+1):\n",
    "            if i not in nums_set:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        count = set(nums)\n",
    "        res = []\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if i not in count:\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        counter = set(nums)\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i in range(1, n+1):\n",
    "            if i not in counter:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)+1\n",
    "        \n",
    "        res=[]\n",
    "        nums1 = set(nums)\n",
    "        for i in range(1,n):\n",
    "            if i not in nums1:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        numss=list(set(nums))\n",
    "        numss.append(0)\n",
    "        a=[]\n",
    "        b=0\n",
    "        for i in range(1,len(nums)+1): \n",
    "            if i!=numss[b]:      \n",
    "                a.append(i)\n",
    "            else:\n",
    "                b=b+1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        all_num = set(range(1, n+1))\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] in all_num:\n",
    "                all_num.discard(nums[i])\n",
    "        \n",
    "        return list(all_num)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        m = len(nums)\n",
    "        start = 0\n",
    "        value = 1\n",
    "        while value <= n:\n",
    "            if nums[start] == value:\n",
    "                if start < m - 1:\n",
    "                    start = start + 1\n",
    "            else:\n",
    "                res.append(value)\n",
    "            value = value + 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "      ans = set(range(1, len(nums)+1))\n",
    "      for num in nums:\n",
    "        ans.discard(num)\n",
    "      return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=set([i for i in range(1, n+1)])\n",
    "        for num in nums:\n",
    "            if num in ans:\n",
    "                ans.remove(num)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findDisappearedNumbers(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        counter = set(nums)\n",
    "        N = len(nums)\n",
    "        res = []\n",
    "        for i in range(1, N + 1):\n",
    "            if i not in counter:\n",
    "                res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        tmp = [x for x in range(1, len(nums)+1)]\n",
    "        nums = list(set(nums))\n",
    "        res = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        nums.sort()\n",
    "        print(nums, tmp)\n",
    "        while i < len(tmp) and j < len(nums):\n",
    "            if tmp[i] < nums[j]:\n",
    "                res.append(tmp[i])\n",
    "            else:\n",
    "                j += 1\n",
    "            i += 1\n",
    "        if i < len(tmp):\n",
    "            res += tmp[i:]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        import random\n",
    "        def paration(begin,end):\n",
    "            if begin >= end:\n",
    "                return\n",
    "            else:\n",
    "                provit_idx = random.randint(begin,end)\n",
    "                provit = nums[provit_idx]\n",
    "                nums[begin], nums[provit_idx] = nums[provit_idx], nums[begin]\n",
    "                left, right = begin, end\n",
    "                while left < right:\n",
    "                    while left < right and nums[right] >= provit:\n",
    "                        right -= 1\n",
    "                    while left < right and nums[left] <= provit:\n",
    "                        left += 1\n",
    "\n",
    "                    if left < right:\n",
    "                        nums[left], nums[right] = nums[right], nums[left]\n",
    "\n",
    "                nums[begin], nums[left] = nums[left], nums[begin]\n",
    "                paration(begin, left - 1)\n",
    "                paration(left + 1, end)\n",
    "\n",
    "        length = len(nums)\n",
    "        paration(0, length - 1)\n",
    "        res = []\n",
    "        times, idx = 0, 1\n",
    "        while times < length - 1:\n",
    "            if nums[idx] == nums[idx - 1]:\n",
    "                nums.pop(idx)\n",
    "                nums.append(0)\n",
    "            else:\n",
    "                idx += 1\n",
    "            times += 1\n",
    "\n",
    "        times, idx = 0, 0\n",
    "\n",
    "        while times < length:\n",
    "            if nums[idx] == times + 1:\n",
    "                idx += 1\n",
    "            elif nums[idx] < times + 1:\n",
    "                idx += 1\n",
    "                res.append(times + 1)\n",
    "            else:\n",
    "                res.append(times + 1)\n",
    "\n",
    "            times += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        return list(set(range(1, len(nums) + 1)) - set(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        ans = []\n",
    "        for num in nums:\n",
    "            dic[num] += 1\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if dic[i] == 0:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        lst=list(set(copy.deepcopy(nums)))\n",
    "        i=1\n",
    "        ans=[]\n",
    "        a=len(nums)\n",
    "        while i<=a:\n",
    "            if len(lst)!=0 and i!=lst[0]:\n",
    "                ans.append(i)\n",
    "                i+=1\n",
    "            elif len(lst)==0:\n",
    "                ans.append(i)\n",
    "                i+=1\n",
    "            else:\n",
    "                # while len(lst)!=0 and lst[0]==i:\n",
    "                lst.remove(i)\n",
    "                i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        list2 = [i for i in range(1, len(nums)+1)]\n",
    "        set1 = set(nums)\n",
    "        set2 = set(list2)\n",
    "        return list(set2 - set1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nl = [i for i in range(1, n+1)]\n",
    "        return list(set(nl).difference(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        lis = []\n",
    "        for i in range(1,len(nums) + 1):\n",
    "            lis.append(i)\n",
    "        num = set(lis)-set(nums)\n",
    "        return list(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        hash = {}\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            hash[i] = 1\n",
    "\n",
    "        for n in nums:\n",
    "            if hash.get(n):\n",
    "                hash[n] -= 1\n",
    "        return [n for n in hash if hash.get(n) == 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        return list(set(range(1,len(nums)+1)).difference(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        return(list(set(range(1, len(nums) + 1)) - set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        return list(set(range(1, len(nums) + 1)).difference(set(nums)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        return list(set(range(1, len(nums) + 1)).difference(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        return list(set(range(1, len(nums) + 1)).difference(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        return list(set(range(1, n+1)) - set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        se = set(nums)\n",
    "        set_N = set(range(1,len(nums)+1))\n",
    "        res = list(set_N-se)\n",
    "\n",
    "        \n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        nums2=set(nums)\n",
    "        s=set()\n",
    "        for i in range(1,n+1):\n",
    "            s.add(i)\n",
    "        ans=s-nums2\n",
    "        res=list(ans)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        return list(set(range(1,len(nums)+1)) - set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        return list(set(range(1,len(nums)+1)) - set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        t = []\n",
    "        for i in range(1, n+1):\n",
    "            t.append(i)\n",
    "        tt = set(t) - set(nums)\n",
    "        return list(tt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:\n",
    "        nums1 = []\n",
    "        for i in range(1,len(nums)+1):\n",
    "            nums1.append(i)\n",
    "        return list(set(nums1) - set(nums))  # set为列表变集合，可以使用差集找到缺失的数字\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
